1. Field of the Invention
The present invention relates to an image processing apparatus, image processing method, computer-readable medium, which vectorize an image and, more particularly, to an image processing method which implements vectorization to be free from any gaps between color regions by extracting boundary lines between color regions from contour information of the color regions (regions each of which includes pixels that can be considered as the same color), and reconstructing original color regions after function approximation of the boundary lines.
2. Description of the Related Art
As techniques associated with vectorization of images, a contour information extraction method and coordinate point sequence function approximation method have been proposed in addition to methods for characters. Furthermore, targets are broadened to general illustration images, and techniques for applying vectorization processing to various types of images such as vectorization for line images, and that for color images have been proposed.
Vectorized data allows smooth contour expression free from any jaggies when it is zoomed to a desired size. For an illustration image and the like, vectorization also has a data size reduction effect, and allows, for example, easy edit processing in a computer. Most of images such as characters and line images can be handled as binary images or single-color images (those in which characters and line parts are defined by a single color, and a remaining part corresponds to a white background). For these images, when contours extracted for respective color-connection regions (those of characters and line images) undergo function approximation, a preferred vectorization result can be obtained. Note that a color-connection region (color region) is a region that includes connected pixels determined to have the same color (that in which same color pixels are connected). However, most of illustrations include many colors, and how to handle boundary lines between a plurality of color regions poses a problem. When contours of color regions detected from a multi-color image undergo function approximation in the same manner as in the processing for a binary image, the contours of respective neighboring color regions are individually approximated. In this case, two approximate curves are obtained for a common boundary line part between neighboring color regions due to approximation errors, and gaps and overlaps are often generated. FIGS. 3A and 3B show this state. FIG. 3A shows an example in which contour shapes of respective color regions are extracted from an input image. Assuming that a region of a white background part is not counted, there are three color regions which neighbor other color regions (which have boundary lines with other regions). FIG. 3B shows a processing result obtained when contour information shown in FIG. 3A individually undergoes function approximation for each color region, and gaps and an overlap are generated between the color regions.
A vectorization method which prevents gaps from being generated between color regions based on the aforementioned problem has also been proposed. For example, in Japanese Patent Laid-Open No. 2006-031245, a boundary between pixels having a given color difference or more is tracked as a contour, a point where pixels of three or more colors meet is selected as a branch point, and partial contours for respective branch points are extracted. To have a partial contour as a processing unit of function approximation, data after the function approximation are connected again to generate vector data, thus applying a common function approximation result to boundary lines.
In Japanese Patent Laid-Open No. 2008-146496, an image is scanned in a horizontal direction, vertical direction, and oblique direction to extract boundary pixels, and region numbers which neighbor at respective boundaries are stored. Then, boundary pixel coordinates and region numbers which neighbor at respective boundary pixels, which are detected upon scanning in the horizontal direction, are stored in a horizontal direction boundary point table. Also, a vertical direction boundary point table and oblique direction boundary point table are similarly generated for the vertical direction and oblique direction. Of boundary points which are included in at least two or more tables of the three tables, a point where combinations of neighboring region numbers on the two or more tables do not perfectly match is selected as an intersection. That is, in Japanese Patent Laid-Open No. 2008-146496 as well, a boundary point where three or more color regions meet is selected as an intersection. An extracted intersection of color regions is used as an end point, and a contour coordinate point sequence which connects between end points is generated as a boundary line. After the boundary lines undergo function approximation, data after the function approximation are connected again to generate vector data. In this processing as well, a common function approximation result is applied to the boundary lines as in Japanese Patent Laid-Open No. 2006-031245.
In general, there are two concepts of a connection state between pixels in image data. The first connection state is the concept of 4-neighboring connection (4-connectivity) in which pixels in four directions, that is, upper, lower, right, and left directions are scanned to have a pixel of interest as a center, and when a pixel having a pixel value of the same color is found, it is determined that the pixel of interest and the pixel of the same color are connected. The second connection state is the concept of 8-neighboring connection (8-connectivity) in which pixels in eight directions, that is, upper, lower, right, left, and oblique directions are scanned to have a pixel of interest as a center, and when a pixel having a pixel value of the same color is found, it is determined that the pixel is connected to the pixel of interest. That is, as for a position where the pixels of the same colors neighbor in only the oblique directions, it is determined that these pixels are not connected since the oblique directions are not scanned in the 4-neighboring connection concept. On the other hand, based on the 8-neighboring connection concept, even when pixels of the same colors neighbor in only the oblique directions, it is determined that they are connected. Hence, these pixels are handled as one pixel group (the same color region).
FIG. 4 shows an image which includes pixels of two colors, that is, white and gray, and includes a position where pixels of the same colors are connected in the oblique directions. In this case, respective contours are extracted as follows by applying the 8-neighboring connection concept to white and gray regions. For example, assume that an inside contour of a gray region and outside contours of white regions included in the gray region are to be extracted, and respective contour extraction processes progress in the direction of the solid arrow. At this time, the next extraction direction to progress includes two directions, that is, upper and lower directions from an intersection. When an inside contour of the gray region is to be extracted based on the 8-neighboring connection concept, since it is considered that gray pixels which neighbor in an oblique direction are connected, an upper direction is set as the next extraction direction. On the other hand, when an outside contour of the white region is to be extracted based on the 8-neighboring connection concept, since it is considered that white pixels which neighbor obliquely are connected, a lower direction is set as the extraction direction. That is, even when either an outside or inside contour is to be extracted based on the 8-neighboring connection concept, although the gray and white regions have a common boundary, the contour extraction direction unwantedly changes. Hence, contour shapes extracted finally do not match.
In the example of FIG. 4, two inside contours of the gray region are extracted based on the 8-neighboring connection concept. Also, when an outside contour of the white region is extracted based on the 8-neighboring connection concept, since contour extraction progresses while determining that neighboring positions in the oblique direction are connected, one outside contour is extracted. In this manner, when the two inside contours of the gray region and one outside contour of the white region, which are extracted in this way, respectively undergo function approximation, different function approximation results are obtained, thus causing gaps and overlaps.
On the other hand, in Japanese Patent Laid-Open No. 2006-031245, since a point where pixels of three or more colors meet is selected as a branch point, a position where pixels of the same colors neighbor in the oblique directions, as shown in FIG. 4, is not considered as a branch point since there are only two colors.
The method disclosed by Japanese Patent Laid-Open No. 2008-146496 handles pixel positions themselves as a coordinate point sequence in place of a contour of pixels. Hence, a boundary line of a thin line having a 1-pixel width cannot be correctly extracted. Furthermore, in Japanese Patent Laid-Open No. 2008-146496, a point where combinations of region numbers stored in the boundary point tables do not match (that is, a point where regions of three colors meet) is selected as an intersection. Therefore, in Japanese Patent Laid-Open No. 2008-146496 as well, a position where pixels of the same colors neighbor in the oblique directions, as shown in FIG. 4, is not considered as an intersection since there are only two colors.
Therefore, even when the techniques of Japanese Patent Laid-Open Nos. 2006-031245 and 2008-146496 are used, a contour is not divided at a position where pixels of the same colors neighbor in only the oblique directions, as shown in FIG. 4, gaps and overlaps are generated when boundary lines of contours undergo function approximation.